package com.cuz.for2024;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class T5 {

    public static void main(String[] args) {

        System.out.println(new T5().longestPalindrome2("cbbd"));
    }
    public String longestPalindrome2(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        char[] charArray = s.toCharArray();
        int max = 1;
        int start = 0;
        int end = 0;
        for (int i = 1; i < charArray.length; i++) {
            int len1 = expend(charArray, i, i);
            int len2 = expend(charArray, i, i + 1);
            if (len1 > max) {
                max = len1;
                start = i - len1 / 2;
                end = i + len1 / 2;
            }
            if (len2 > max) {
                max = len2;
                // i = 1,len2=2
                // cbbd
                start = i - (len2 - 1) / 2;
                end = i+1 + (len2 - 1) / 2;
            }
        }
        return s.substring(start, end+1);
    }

    private int expend(char[] charArray, int start, int end) {
        while (start >= 0 && end < charArray.length) {
            if (charArray[start] == charArray[end]) {
                start--;
                end++;
            } else {
                break;
            }

        }
        return end - start - 1;
    }
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        char[] charArray = s.toCharArray();

        boolean dp[][] = new boolean[charArray.length][charArray.length];
        for (int i = 0; i < charArray.length; i++) {
            dp[i][i] = true;
        }
        int maxLen = 1;
        int start = 0;
        int end = 1;

        for (int j = 1; j < charArray.length; j++) {
            for (int i = 0; i < j; i++) {
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                    continue;
                }
                if (j - i <= 2) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }

                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                    end = j + 1;
                }
            }
        }
        return s.substring(start, end);
    }
}
